//「一本通 3.1 例 1」黑暗城堡
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN=1000;
const int INF=0x7fffffff;
int dis[MAXN+1];
bool visited[MAXN+1];
struct Channel
{
    int to;
    int len;
};
struct  Room
{
    int id;
    bool operator <(const Room other)const {
        return dis[id]>dis[other.id];
    }
};
priority_queue<Room> heap;
vector<Channel> G[MAXN+1];
int n,m;
long long ans;
//求最短路径
void dijkstra(){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    heap.push({1});
    while(!heap.empty()){
        int u=heap.top().id;
        heap.pop();
        visited[u]=true;
        for(int k=0;k<G[u].size();k++){
            Channel ch=G[u][k];
            int v=ch.to;
            int w=ch.len;
            if (!visited[v]&&dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                heap.push({v});
            }
        }
    }
}
//查找每个点有几种途径取得最短路径，累乘就是方案数
void solve(){
    ans=1;
    for(int u=2;u<=n;u++){
        int p=0;
        for(int k=0;k<G[u].size();k++){
            Channel ch=G[u][k];
            int v=ch.to;
            int w=ch.len;
            if (dis[u]==dis[v]+w) p++;
        }
        ans=(ans*p)%INF;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dijkstra();
    solve();
    cout<<ans;
}

